package bfsalgorithm;

import java.util.*;

/**
 * 207.课程表
 */
public class Exercise12 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 拓扑排序
        int[] in = new int[numCourses]; //统计每一个值的入度的个数
        Map<Integer, List<Integer>> edges = new HashMap<>(); // 对于这个课程进行建图
        for(int i = 0;i < prerequisites.length;i++) {
            int a = prerequisites[i][0],b = prerequisites[i][1]; // b -> a
            if(!edges.containsKey(b)) {
                edges.put(b,new ArrayList<>());
            }
            // 把a这个值，放入到对应的b这个对应的HashMap中
            edges.get(b).add(a);
            in[a]++; // 这个a数据，就会增加一个入度
        }

        // BFS进行拓扑排序
        Queue<Integer> q = new LinkedList<>();
        // 把入队为0的数据放入到队列中
        for(int i = 0;i < numCourses;i++) {
            if(in[i] == 0) {
                q.add(i);
            }
        }

        // 进行BFS
        while(!q.isEmpty()) {
            int t = q.poll(); // 取出队顶数据
            // 把这个t数据从图中删除，并且把其连线删除
            for(int a : edges.getOrDefault(t,new ArrayList<>())) {
                // 这里最后一个数据是没有延伸值的，那么就将其置为空
                in[a]--;
                if(in[a] == 0) {
                    q.add(a);
                }
            }
        }

        // 进行判断是否还存在值没有进行排序，也就是是否还有环
        // 那么就可以去判断 0-numCourses-1 这些值对应的入度是否为0。不为0就存在环
        for(int i = 0;i < numCourses;i++) {
            if(in[i] != 0) {
                return false;
            }
        }

        return true;
    }
}
